"""
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
"""
from typing import List


class Solution:
    def dfs(self, nums, k):
        if k == len(nums):
            self.ans.append(self.tmp[:])
            return
        self.tmp.append(nums[k])
        self.dfs(nums, k + 1)
        self.tmp.pop()
        self.dfs(nums, k + 1)

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.ans = []
        self.tmp = []
        self.dfs(nums, 0)
        return self.ans


nums = [1, 2, 3]
a = Solution()
print(a.subsets(nums))
